package leetcode.code0731;

public class MyCalendarTwo {

	class Node {
		private int Start;
		private int End;
		private int Mid;
		private int bookTimes;
		private int bookTimesCache;
		private Node Left;
		private Node Right;

		public Node(int start, int end) {
			this.Start = start;
			this.End = end;
			this.Mid = ((end - start) >> 1) + start;
		}

		public Node getLeft() {
			if (this.Left == null) {
				this.Left = new Node(this.Start, this.Mid);
			}
			return this.Left;
		}

		public Node getRight() {
			if (this.Right == null) {
				this.Right = new Node(this.Mid + 1, this.End);
			}
			return this.Right;
		}

		public void book(int l, int r) {
			if (this.Start == l && this.End == r) {
				this.bookTimes += 1;
				this.bookTimesCache += 1;
				return;
			}
			this.pushDown();
			if (r <= this.Mid) {
				this.getLeft().book(l, r);
			} else if (l > this.Mid) {
				this.getRight().book(l, r);
			} else {
				this.getLeft().book(l, this.Mid);
				this.getRight().book(this.Mid + 1, r);
			}
			this.pushUp();
		}

		public int maxBookTimes(int l, int r) {
			if (this.Start == l && this.End == r) {
				return this.bookTimes;
			}
			int ans = 0;
			this.pushDown();
			if (r <= this.Mid) {
				ans = this.getLeft().maxBookTimes(l, r);
			} else if (l > this.Mid) {
				ans = this.getRight().maxBookTimes(l, r);
			} else {
				ans = Math.max(this.getLeft().maxBookTimes(l, this.Mid), this.getRight().maxBookTimes(this.Mid + 1, r));
			}
			this.pushUp();
			return ans;
		}

		private void pushUp() {
			this.bookTimes = Math.max(this.getLeft().bookTimes, this.getRight().bookTimes);
		}

		private void pushDown() {
			if (this.bookTimesCache != 0) {
				Node l = this.getLeft();
				l.bookTimes += this.bookTimesCache;
				l.bookTimesCache += this.bookTimesCache;
				Node r = this.getRight();
				r.bookTimes += this.bookTimesCache;
				r.bookTimesCache += this.bookTimesCache;
				this.bookTimesCache = 0;
			}
		}

	}

	private Node root;

	public MyCalendarTwo() {
		root = new Node(0, (int) 1e9);
	}

	public boolean book(int start, int end) {
		if (root.maxBookTimes(start, end - 1) == 2) {
			return false;
		}
		root.book(start, end - 1);
		return true;
	}

	public static void main(String[] args) {
		MyCalendarTwo MyCalendar = new MyCalendarTwo();
		book(MyCalendar, 10, 20); // returns true
		book(MyCalendar, 50, 60); // returns true
		book(MyCalendar, 10, 40); // returns true
		book(MyCalendar, 5, 15); // returns false
		book(MyCalendar, 5, 10); // returns true
		book(MyCalendar, 25, 55); // returns true

	}

	public static void book(MyCalendarTwo MyCalendar, int a, int b) {
		boolean ans = MyCalendar.book(a, b);
		System.out.println(ans);
	}

}
